import java.util.*;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 26
 * Time: 17:36
 */
//力扣692. 前K个高频单词
public class Solution5 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        //统计每个单词出现的次数
        for (String word : words) {
            if(map.get(word) == null) {
                map.put(word, 1);
            }else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //创建堆，PriorityQueue构造方法的参数传实现了比较器的类的对象
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>
                (new Comparator<Map.Entry<String, Integer>>() {//传匿名内部类对象，这个匿名内部类实现了比较器接口
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                      return o2.getKey().compareTo(o1.getKey());//以单词字母排序创建大根堆，HashMap中的Node类实现了Map.Entry<K,V>接口，Node类中有getKey()和getValue()方法
                }
                return o1.getValue() - o2.getValue();//以单词的频率创建小根堆
            }
        });
        //遍历map，调整优先级队列
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {//堆还没创建好时，先创建堆
                minHeap.offer(entry);
            }else {//堆创建好了，调整堆
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //字母小的进堆顶
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    //单词的频率大的进堆顶
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);//注意这里要反转顺序表
        return ret;
    }
}
